/*
题目: 尽可能使字符串相等
给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

https://leetcode.cn/problems/get-equal-substrings-within-budget
 */
public class EqualSubstring {
    int n ;
    public int equalSubstring(String s, String t, int maxCost) {
        // 前缀和 + 二分查找
        // 前缀和 是 递增的, 对于每一个 i 找到第一个小于 maxCost 的 prefix[i] - prefix[j] (j < i), 的最大长度
        n = s.length();
        // 前缀和 : nums[left : right] = prefix[right + 1] - prefix[left], 长度 : right - left + 1;
        // 前缀和 中 两个下标对应的前缀和相减 prefix[big] - prefix[sma] 就是 实际数组 中对应的长度
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i ++) {
            prefix[i + 1] = prefix[i] + Math.abs((int) (t.charAt(i) - s.charAt(i)));
        }

        int maxn = 0;
        // 从 1 开始遍历 前缀和 数组
        for (int i = 1; i <= n; i ++) {
            // prefix[i] - prefix[j] <= maxCost 找到最小的 prefix[j]
            int pos = binarySearch(prefix, 0, i - 1, prefix[i] - maxCost);
            maxn = Math.max(maxn, i - pos);
        }

        return maxn;
    }

    // 左闭右闭, prefix[index] >= prefix[i] - maxCost 中 index 最小的下标
    private int binarySearch(int[] prefix, int left, int right, int tar) {
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (prefix[mid] >= tar) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // right + 1 是答案, 仅需要考虑 left 的极端情况 即可
        return right + 1;
    }
}
